package 小测试;

/**
 * Created by Administrator on 2017/9/4.
 */
public class MyBinarySearch {
    /**
     * @param arr 被查找的数组
     * @param key 要查找的值
     * @return 返回在数组中的索引
     */
    public static int myBinarySearch(int[] arr, int key) {
        //初始左右边界索引
        int left = 0;
        int right = arr.length - 1;

        //遍历整个数组
        while(left<=right){
            int mid=(left+right)>>>1; //不用除2的方法，是因为对于一个足够大的数组长度，如1100000000，mid会计算得负数
            int midVal=arr[mid];
            if(midVal<key){
                left=mid+1;
            }else if(midVal>key){
                right=mid-1;
            }else
                return mid;  //key值被找到
        }
        //没有找到指定的值是，返回最后左边界的索引
        return -(left+1);  //key值没找到
    }
}
